// 位图的实现
// Bitset是一种能以紧凑形式存储位的数据结构
// Bitset(int n) : 初始化n个位，所有位都是0
// void fix(int i) : 将下标i的位上的值更新为1
// void unfix(int i) : 将下标i的位上的值更新为0
// void flip() : 翻转所有位的值
// boolean all() : 是否所有位都是1
// boolean one() : 是否至少有一位是1
// int count() : 返回所有位中1的数量
// String toString() : 返回所有位的状态
// 测试链接 : https://leetcode-cn.com/problems/design-bitset/
public class DesignBitsetTest {
    class Bitset {
        public int[] set;
        public int Bsize;
        public int zeros;
        public int ones;
        public boolean reverse; //false 表示正常的1，0  true为1表示0，0表示1

        public Bitset(int size) {
            set = new int[size+31/32];
            ones = 0;
            zeros = size;
            reverse = false;
            Bsize = size;
        }

        public void fix(int idx) {  //将下标i的位上的值更新为1
            int index = idx / 32;
            int bit = idx % 32;
            if(!reverse) {  //正常表示
                if( ( set[index] >> bit & 1)  == 1){ //如果原本就是1不做处理
                    return;
                }else {
                    set[index] |= ( 1 << bit );  //将该位置上的0变1
                    ones++;
                    zeros--;
                }
            }else { //0表示1，1表示0
                if( ( set[index] >> bit & 1)  == 0){ //如果原本就是0不做处理
                    return;
                }else {
                    set[index] ^= ( 1 << bit ); //将该位置上的1变0
                    ones++;
                    zeros--;
                }
            }
        }

        public void unfix(int idx) { //将下标i的位上的值更新为0
            int index = idx / 32;
            int bit = idx % 32;
            if(!reverse) {  //正常表示
                if( ( set[index] >> bit & 1)  == 0){ //如果原本就是0不做处理
                    return;
                }else {
                    set[index] ^= ( 1 << bit );  //将该位置上的1变0
                    ones--;
                    zeros++;
                }
            }else { //0表示1，1表示0
                if( ( set[index] >> bit & 1)  == 1){ //如果原本就是1不做处理
                    return;
                }else {
                    set[index] ^= ( 1 << bit ); //将该位置上的0变1
                    ones--;
                    zeros++;
                }
            }
        }

        public void flip() {  //翻转所有位的值
            reverse = !reverse;
            //交换0和1的数量
            int temp = ones;
            ones = zeros;
            zeros = temp;
        }

        public boolean all() { //是否所有位都是1
            return ones == Bsize;
        }

        public boolean one() { //是否至少有一位是1
            return ones > 0;
        }

        public int count() { //返回所有位中1的数量
            return ones;
        }

        public String toString() { //返回所有位的状态
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < Bsize; i++) {
                int index = i/32;
                int bit = i%32;
                if(!reverse) {
                    if((set[index] >> bit & 1) == 1 ){
                        sb.append(1);
                    }else {
                        sb.append(0);
                    }
                }else {
                    if((set[index] >> bit & 1) == 1 ){
                        sb.append(0);
                    }else {
                        sb.append(1);
                    }
                }
            }
            return sb.toString();
        }
    }

}
